iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 1
1
自我挑戰組

神羅天征! 一起(爆肝)征服程式解題系列 第 1

[Day 1] LeetCode - 739 Daily Temperatures

  • 分享至 

  • xImage
  •  

本篇同步發布於Blog: [解題] LeetCode - 739 Daily Temperatures

平台:

LeetCode

題號:

739 - Daily Temperatures

題目連結:

https://leetcode.com/problems/daily-temperatures/

題目說明:

        輸入一個n大小陣列T,求第x天的溫度T,要經過y天是否會遇到比溫度T還高,有的話標記第x天的答案為y,否則為0。

       比如範例輸入的[73, 74, 75, 71, 69, 72, 76, 73], 

  1. 第1天的溫度73度只隔1天就遇到比它高溫的74度,所以標記為1
  2. 第2天的溫度74度只隔1天就遇到比它高溫的75度,所以標記為1
  3. 第3天的溫度75度需隔4天才遇到比它高溫的76度,所以標記為4

      最終的答案為[1, 1, 4, 2, 1, 1, 0, 0] 。

解題方法:

      使用Stack,將第x天溫度的x值push至此stack。當stack不為空時,檢查是否第y天的溫度有高於目前stack的top對應的溫度,如果有則可算出y - x為第x天的答案;如果沒有高於stack top的溫度則換下一天。

     以前面範例輸入為例:

 1. Stack[] 現在是空的, 增加為Stack[0]

    2. 第2天是74度,74度 > T[Stack.top] = 73,所以ans[0] = 1 - 0 = 1,而Stack.pop()後已經空了,再push(1),變成Stack[1]。

    3. 第3天是75度,75度 > T[Stack.top] = 74,所以ans[1] = 2 - 1 = 1,而Stack.pop()後已經空了,再push(2),變成Stack[2]。

 4. 第4天是71度,71度 < T[Stack.top] = 75,換下一天,並push(3),變成Stack[2, 3]。

 5. 第5天是69度,69度 < T[Stack.top] = 71,換下一天,並push(4),變成Stack[2, 3, 4]。

    6. 第6天是72度,72度 > T[Stack.top] = 69,所以ans[4] = 5 - 4 = 1,Stack.pop()換下一個,72度 > T[Stack.top] = 71,所以ans[3] = 5 - 3 = 2,Stack.pop()換下一個,72度 < T[Stack.top] = 75,換下一天,並push(5),變成Stack[2, 5]。

 7. 第7天是76度,76度 > T[Stack.top] = 72,所以ans[5] = 6 - 5 = 1,Stack.pop()換下一個,76度 > T[Stack.top] = 75,所以ans[2] = 6 - 2 = 4,而Stack.pop()後已經空了,再push(6),變成Stack[6]。

 8. 第8天是73度,73度 < T[Stack.top] = 76,換下一天,並push(7),變成Stack[6, 7]。
  
    剩下沒被標記答案的都是0。

難度為Medium

程式碼 (C++ 與 C#):

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st;
        int size = T.size();
        vector<int> ans = vector<int>(size, 0);

        for(int i = 0 ; i < size;++i){
            while(!st.empty()){
                if(T[i] > T[st.top()]){
                    ans[st.top()] = i - st.top();
                    st.pop();
                }
                else{
                    break;
                }
            }

            st.push(i);
        }
        
        return ans;
    }
};


int main()
{
	vector<int> T{73, 74, 75, 71, 69, 72, 76, 73}; 
	Solution sol;
	vector<int> ans = sol.dailyTemperatures(T);
    
	for(int i = 0 ; i < ans.size();++i){
		cout << ans[i] << endl;
	}

    return 0;
}

using System;
using System.Collections.Generic;

namespace LeetCode739
{
    public class Solution {
        public int[] DailyTemperatures(int[] T) {
            Stack<int> st = new Stack<int>();
            int size = T.Length;

            int[] ans = new int[size];

            for(int i = 0 ; i < size;++i){
                while(st.Count > 0){
                    if(T[i] > T[st.Peek()]){
                        ans[st.Peek()] = i - st.Peek();
                        st.Pop();
                    }
                    else{
                        break;
                    }
                }

                st.Push(i);
            }
        
            return ans;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int[] t = new int[] {73, 74, 75, 71, 69, 72, 76, 73};
            int[] ans = new Solution().DailyTemperatures(t);
            
            foreach (int item in ans)
            {
                Console.WriteLine(item);
            }

            Console.ReadLine();
        }
    }
}

GITHUB位置(C++ 與 C#):

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/700-799/739.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/700-799/739.cs


下一篇
[Day 2] LeetCode - 455 Assign Cookies
系列文
神羅天征! 一起(爆肝)征服程式解題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言